Lucas[數論定理]

Lucas[數論定理]

Lucas定理是用來求 c(n,m) mod p,p為素數的值。

定律定義

Lucas定理:我們令 n=sp+q , m=tp+r . (q ,r ≤p)

那么:

Lucas[數論定理] Lucas[數論定理]
Lucas[數論定理] Lucas[數論定理]

(在編程時你只要繼續對 調用Lucas定理即可。

代碼可以遞歸的去完成這個過程,其中遞歸終點為 t = 0

時間 O(log (n)*p):)

推導過程

Lucas定理證明:

Lucas[數論定理] Lucas[數論定理]

首先你需要這個算式: ,其中f > 0&& f < p,然後

(1 + x) Ξ(1 + x) Ξ( (1 + x))· (1 + x)Ξ(1 + x) · (1 + x) (mod p)

Lucas[數論定理] Lucas[數論定理]
(modp)
Lucas[數論定理] Lucas[數論定理]

所以得(1 + x)

(mod p)
Lucas[數論定理] Lucas[數論定理]

我們求左邊 (1 + x)中的 的係數為:

Lucas[數論定理] Lucas[數論定理]
Lucas[數論定理] Lucas[數論定理]

求右邊公式中的 為:

Lucas[數論定理] Lucas[數論定理]

通過觀察你會發現若且唯若i = t , j = r ,能夠得到

的係數,即
Lucas[數論定理] Lucas[數論定理]

 

所以

Lucas[數論定理] Lucas[數論定理]

得證。

代碼實現

c++

求C(n, m) mod 10007

見右圖,參考馮志剛《初等數論》第37頁。

相關詞條

熱門詞條

聯絡我們